In a data processing system, instructions and associated data are transferred from storage devices to one or more processors for processing, and then resulting data generated by the processor is returned to storage devices. Thus, typical processing operations involve frequent and repetitive reading and writing from/to storage devices. As a result, storage access delays are often a primary limitation in the performance of a data processing system. Preferably, therefore, storage access speed should be maximized to maximize performance. However, often cost and other constraints require that the storage devices be comprised of relatively long access time circuitry, e.g., hard disk rives. To overcome the resulting performance rawbacks, caches are typically used.
A cache typically includes a relatively small, but relatively high speed, bank of memory, that can be more rapidly accessed by the processor(s) than the storage device that the cache services. A write cache is used to temporarily store data being written by the processor to a storage device. The processor writes data into the write cache, and thereafter the data is transferred or destaged from the write cache to the appropriate storage device. A read cache duplicates memory locations in the storage device, so that when a particular storage location being accessed by the processor is duplicated in the read cache, the processor may rapidly access the read cache instead of waiting for access to the storage device.
Typically, a cache is associated with a cache directory, which stores an indication of those memory locations currently stored in the cache. Thus, when a processor requests access to a particular memory location, the cache directory is accessed to determine whether that memory location is in the cache. If so, the requested memory location may be accessed in the cache, if appropriate. If the memory location is not in the cache, the accessed memory location may be established in the cache, if appropriate.
Typically, sequential locations on a storage device can be read or written rapidly. For example, a disk drive may be arranged into tracks and sectors, so that sequential data in sequential tracks and sectors can be rapidly read or written. However, it is also typical to incur long access delays when reading or writing data at disparate locations. For example, a disk drive typically incurs a substantial delay to transfer from one track and sector to another, non-adjacent track and sector.
In light of the rapid access that can be made to sequential locations on a storage device, caches are typically organized into "lines", which are relatively long sequences of sequential storage locations. Typically, when storage locations are written into a write cache, the data written into the cache is arranged into cache lines, and then sequential locations from one or more sequential cache lines are destaged to the storage device at one time. Similarly, when memory locations are duplicated into a read cache, typically the needed memory location as well as neighboring memory locations, are brought into a line of the cache.
Data is typically destaged from a write cache in the order in which it is written to the cache, i.e., first-in, first-out. This approach, however, can lead to various difficulties.
For example, while sequential storage locations are often written sequentially in time, this is not always the case. Consider, for example, a processing thread that writes to sequential storage locations in a first range of storage location on a storage device, and then writes to sequential storage locations in a second range of storage locations which is adjacent to the first range. If the second range is located at higher storage addresses than the first range of storage locations, then the first range should be destaged before the second range, and in this case a destage algorithm which destages memory locations in the order in which they were written to the cache, can operate efficiently. However, if the second range of storage locations is at lower storage addresses than the first range, then the second range should be destaged before the first range, and in this case a destage algorithm which destages memory locations in the order in which they were written in the cache will operate inefficiently, because the first range will be destaged first.
As a further example, when an exceptionally large amount of data is written to the cache in one operation, a sizeable percentage of the cache will be consumed. A large block of data of this kind should be destaged as soon as possible to free space in the cache. Unfortunately, if a first-in, first-out strategy is used in destaging the data, this large percentage of the cache will remain consumed until all previously written data has been destaged. The resulting delay can cause the cache to become full, preventing additional write operations and delaying processing.